// 运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制 。
// 实现 LRUCache 类：

// LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
// int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
// void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/lru-cache
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<list>
#include<unordered_map>
#include<set>
#include<queue>
using namespace std;

// 采用STL(标准模板库)
// 看了题解
// 执行用时：
// 408 ms
// , 在所有 C++ 提交中击败了
// 45.47%
// 的用户
// 内存消耗：
// 161.1 MB
// , 在所有 C++ 提交中击败了
// 44.38%
// 的用户

class LRUCache {
public:
    int size;
    list<pair<int,int>> li;
    unordered_map<int,list<pair<int,int>>::iterator> map; 

    LRUCache(int capacity) {
        this->size = capacity;
    }
    
    int get(int key) {
        if(map.find(key)==map.end()){
            return -1;
        }
        else{
            li.splice(li.begin(),li,map[key]);
            return map[key]->second;
        }
    }
    
    void put(int key, int value) {
        if(get(key)!=-1){
            map[key]->second = value;
        }
        else{
            if(map.size()<this->size){
                li.emplace_front(key,value);
                map[key] = li.begin();
            }
            else{
                int temp = li.back().first;
                li.pop_back();
                map.erase(temp);
                put(key,value);
            }
        }
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */